#include <vector>
#include <string>
#include <functional>
#include <queue>

using namespace std;

// 有序三元组中的最大值 II
class Solution 
{
public:
    long long maximumTripletValue(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> suf_max(n);
        suf_max[n - 1] = nums[n - 1];
        for(int i = n - 2; i >= 0; --i)
        {
            suf_max[i] = max(suf_max[i + 1], nums[i]);
        }       

        long long ret = -1;
        vector<int> prev_max(n);
        prev_max[0] = nums[0];
        for(int i = 1; i < n - 1; ++i)
        {
            prev_max[i] = max(nums[i], prev_max[i - 1]);
            ret = max(ret, (long long)(prev_max[i] - nums[i]) * suf_max[i + 1]);
        }
        return ret;
        
    }
};

// 8038. 收集元素的最少操作次数
class Solution 
{
public:
    int minOperations(vector<int>& nums, int k) 
    {
        int n = nums.size();
        long long u = (2LL << k) - 2; // 1 ~ k
        long long s = 0;
        for(int i = n - 1; ; --i)
        {
            s |= 1LL << nums[i];
            if((s & u) == u) return n - i;
        }    
        return -1;
    }
};

// 将数组分割成最多数目的子数组
class Solution 
{
public:
    int maxSubarrays(vector<int>& nums) 
    {
        int a = -1, ret = 0;
        for(int x : nums)
        {
            a &= x;
            if(a == 0)
            {
                ++ret;
                a = -1;
            }
        }
        return max(ret, 1);
    }
};

// 可以被 K 整除连通块的最大数目
class Solution 
{
public:
    int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) 
    {
        vector<vector<int>> g(n);
        for(auto& e : edges)
        {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }            

        int ret = 0;
        function<long long(int, int)> dfs = [&](int x, int fa)
        {
            long long sum = values[x];
            for(int y : g[x])
            {
                if(y != fa) sum += dfs(y, x);
            }
            ret += sum % k == 0;
            return sum;
        };

        dfs(0, -1);
        return ret;
    }
};

// 有向图访问计数
class Solution {
public:
    vector<int> countVisitedNodes(vector<int>& g) {
        int n = g.size();
        vector<vector<int>> rg(n);
        vector<int> deg(n);
        for(int x = 0; x < n; ++x)
        {
            int y = g[x];
            rg[y].push_back(x);
            ++deg[y];
        }

        queue<int> q;
        for(int x = 0; x < n; ++x)
        {
            if(deg[x] == 0) q.push(x);
        }

        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            int y = g[x];
            if(--deg[y] == 0) q.push(y);
        }

        vector<int> ret(n);
        function<void(int, int)> rdfs = [&](int x, int depth)
        {
            ret[x] = depth;
            for(int y : rg[x])
            {
                if(deg[y] == 0) rdfs(y, depth + 1);
            }
        };

        for(int i = 0; i < n; ++i)
        {
            if(deg[i] <= 0) continue;
            vector<int> ring;
            for(int x = i; ; x = g[x])
            {
                deg[x] = -1;
                ring.push_back(x);
                if(g[x] == i) break;
            }

            for(int x : ring)
            {
                rdfs(x, ring.size());
            }
        }

        return ret;
    }
};

// 图中的最长环
class Solution 
{
public:
    int longestCycle(vector<int>& g) 
    {
        int n = g.size();
        vector<int> deg(n);
        for(int x = 0; x < n; ++x)
        {
            int y = g[x];
            if(y != -1)
            {
                ++deg[y];
            }
        }

        queue<int> q;
        // 拓扑排序，去除入度为 0 的节点
        for(int x = 0; x < n; ++x)
        {
            if(deg[x] == 0) q.push(x);
        }
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            int y = g[x];
            if(y != -1)
            {
                if(--deg[y] == 0) q.push(y);
            }
        }

        int ret = -1;
        for(int x = 0; x < n; ++x)
        {
            if(deg[x] <= 0) continue;
            int ringLen = 1;
            int y = x;
            while(g[y] != x)
            {
                ++ringLen;
                y = g[y];
                // deg[y] 置为 -1，避免重复遍历相同的环
                deg[y] = -1;
            }
            ret = max(ret, ringLen);
        }
        return ret;
    }
};